【题解】 [WC2013]糖果公园 树上带修改莫队 luoguP4074/Uoj58 | Qiuly's blog!

【题解】 [WC2013]糖果公园 树上带修改莫队 luoguP4074/Uoj58

Posted on | Edited on | In | Comments:

毒瘤题目，树上带修改莫队板子题。

关于树上莫队和带修改莫队的文章戳这 $QwQ​$ :[算法]莫队&树上莫队

然后就是将其结合在一起了，结合的话炒鸡简单，就是码量增大…

可以算作一个树上莫队/树上带修改莫队的板子来看。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<cctype>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>

#define ll long long
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define swap(x,y) ((x)^=(y)^=(x)^=(y))

const int N=1e5+24;
const int LogN=20;
const int inf=1e9+9;

inline int IN(){
    int x=0;char ch;bool flag=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return flag?-x:x;
}

int n,m,q,v[N],w[N],c[N];/*test*/
int id[N<<1],in[N],out[N],dep[N],f[N][LogN],sequencelong;/*dfs&lca*/
int head[N],cnt;/*Tree Edge*/
struct Edge{int nxt,to;}G[N<<1];/*Tree Edge*/
int c0,c1,block,tot[N],cl[N],cr[N],vis[N],modify[N];/*MO*/
struct MO{int l,r,lbe,rbe,time,id,lca,ans;}Q[N];/*MO*/
ll now,Ans[N];

bool cmp(MO a,MO b){
    if(a.lbe^b.lbe)return a.lbe<b.lbe;
    if(a.rbe^b.rbe)return a.rbe<b.rbe;
    if(a.time^b.time)return a.time<b.time;
}

inline void add(int u,int v){
    G[++cnt].nxt=head[u],G[cnt].to=v,head[u]=cnt;
    G[++cnt].nxt=head[v],G[cnt].to=u,head[v]=cnt;
}

void Get_Lca_and_sequence(int u,int fa){
    dep[u]=dep[fa]+1,f[u][0]=fa;
    for(int i=1;i<20;++i)f[u][i]=f[f[u][i-1]][i-1];
    id[in[u]=++sequencelong]=u;
    for(int i=head[u];i;i=G[i].nxt)
        if(G[i].to!=fa)Get_Lca_and_sequence(G[i].to,u);
    id[out[u]=++sequencelong]=u;
    return;
}

int Lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    for(int i=19;~i;--i)
        if(dep[u]-(1<<i)>=dep[v])u=f[u][i];
    for(int i=19;~i;--i)
        if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
    return u==v?u:f[u][0];
}

inline void _Main_input(){
    n=IN(),m=IN(),q=IN();/*line 1*/
    for(int i=1;i<=m;++i)v[i]=IN();/*line 2*/
    for(int i=1;i<=n;++i)w[i]=IN();/*line 3*/
    for(int i=1;i<n;++i)add(IN(),IN());/*line 4 to n+2*/
    for(int i=1;i<=n;++i)c[i]=IN();/*line n+3*/
    Get_Lca_and_sequence(1,0);
    block=std::ceil(std::pow(sequencelong,0.66666));
    for(int i=1;i<=q;++i){/*line n+4 to n+4+q*/
        int Type=IN(),x=IN(),y=IN();
        if(Type==1){
            Q[++c1].id=c1,Q[c1].time=c0;
            if(x==y){
                Q[c1].lbe=(Q[c1].l=in[x])/block;
                Q[c1].rbe=(Q[c1].r=in[x])/block;
            }else{
                if(in[x]<in[y]&&out[y]<out[x]){
                    Q[c1].lbe=(Q[c1].l=in[x])/block;
                    Q[c1].rbe=(Q[c1].r=in[y])/block;
                }
                else if(in[y]<in[x]&&out[x]<out[y]){
                    Q[c1].lbe=(Q[c1].l=in[y])/block;
                    Q[c1].rbe=(Q[c1].r=in[x])/block;
                }
                else{
                    if(out[x]<in[y]){
                        Q[c1].lbe=(Q[c1].l=out[x])/block;
                        Q[c1].rbe=(Q[c1].r=in[y])/block;
                        Q[c1].lca=Lca(x,y);
                    }
                    else if(out[y]<in[x]){
                        Q[c1].lbe=(Q[c1].l=out[y])/block;
                        Q[c1].rbe=(Q[c1].r=in[x])/block;
                        Q[c1].lca=Lca(x,y);
                    }
                }
            }
        }else modify[++c0]=x,cl[c0]=c[x],cr[c0]=y,c[x]=y;
    }return;
}

inline void work(int x){
    if(vis[x])now-=1ll*v[c[x]]*w[tot[c[x]]--];
    else now+=1ll*v[c[x]]*w[++tot[c[x]]];
    vis[x]^=1;return;
}

inline void add(int x){
    if(vis[modify[x]]){work(modify[x]);c[modify[x]]=cr[x];work(modify[x]);}
    else c[modify[x]]=cr[x];
}

inline void del(int x){
    if(vis[modify[x]]){work(modify[x]);c[modify[x]]=cl[x];work(modify[x]);}
    else c[modify[x]]=cl[x];
}

inline void _Main_Mo_Solve(){
    std::sort(Q+1,Q+c1+1,cmp);
    int l=1,r=0,nowtime=c0;
    for(int i=1;i<=c1;++i){
        while(nowtime>Q[i].time)del(nowtime--);
        while(nowtime<Q[i].time)add(++nowtime);
        while(l<Q[i].l)work(id[l++]);
        while(l>Q[i].l)work(id[--l]);
        while(r<Q[i].r)work(id[++r]);
        while(r>Q[i].r)work(id[r--]);
        if(Q[i].lca)work(Q[i].lca);
        Ans[Q[i].id]=now;
        if(Q[i].lca)work(Q[i].lca);
    }
}

inline void _Main_output(){
    for(int i=1;i<=c1;++i)
        printf("%lld\n",Ans[i]);
}

int main(){
    _Main_input();
    _Main_Mo_Solve();
    _Main_output();
    return 0;
}

当然，尽管再毒瘤，这个也只是入门的树上带修改莫队的题目。

本文标题:【题解】 [WC2013]糖果公园 树上带修改莫队 luoguP4074/Uoj58

文章作者:Qiuly

发布时间:2019年03月08日 - 00:00

最后更新:2019年03月29日 - 13:55

原始链接:http://qiulyblog.github.io/2019/03/08/[题解]luoguP4074/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。